package LeetCodeHot100TopInterview;

import java.util.HashSet;

public class Q128_LongestConsecutive {
    //最长连续序列
    //不要求数字在原数组中连续 比如 123.. ==> 132 也算 123
    // O(n) => 加一个空间（n）
    public int longestConsecutive(int[] nums) {

        //使用 HashSet
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        int max = 0;
        //...
        //枚举每一个左边界
        //若x数满足左边界  则 x-1 在数组中不存在
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i] - 1)){
                continue;
            }
            //继续查找 i+1 i+2...
            int k = 1;
            while (set.contains(nums[i] + k)){
                k++;
            }
            max = Math.max(max, k);
        }
        return max;
    }

    public static void main(String[] args) {
        Q128_LongestConsecutive fun = new Q128_LongestConsecutive();
        System.out.println(fun.longestConsecutive(new int[]{100, 4, 200, 1, 3, 2}));
    }
}
